4465. The ant

 

There are n sticks lying on the ground. The Ant can move only along the sticks. It can go from one stick to another only if the sticks intersect or touch each other. Help the Ant find out if it can reach the stick y from the stick x.

 

Input. The first line of the input contains number t (1 ≤ t ≤ 100) – the amount of tests. Then t test descriptions follow. The first line of each test contains two integers n and m (1 ≤ n, m ≤ 1000) – the number of stick and the number of queries. Next n lines contain four integers Ax, Ay, Bx, By (-10000 ≤ Ax, Ay, Bx, By ≤ 10000) – the coordinates of the endpoints of a stick. You may consider stick to be straight segment on a plane. The next m lines contain two integers each x and y (1 ≤ x, y ≤ n) which are the queries.

 

Output. For each query print "YES" if the Ant can reach the stick number y from the stick number x, otherwise print "NO".

 

Sample Input

Sample Output

2

3 3

1 3 4 3

3 4 3 1

3 1 5 1

1 2

1 3

2 2

3 3

1 1 3 1

2 1 3 1

3 2 4 1

1 2

1 3

2 3

YES
YES
YES
YES
NO
NO

 

 

РЕШЕНИЕ

геометрия + связность

 

Анализ алгоритма

На плоскости расположено множество палочек (отрезков). Муравей может переползти с одной палочки на другую только если они пересекаются. Определить, сможет ли муравей переползти с палочки y на палочку x.

Рассмотрим граф, в котором вершинам соответсвуют палочки. Между вершинами x и y существует ребро только если x и y пересекаются.

 

Реализация алгоритма

 

#include <stdio.h>

#define MAX 1010

 

int x, y, tests, n, m, i, j;

int ax[MAX], ay[MAX], bx[MAX], by[MAX];

int mas[MAX];

 

int RectanglesIntersects(int x1, int y1, int x2, int y2,

                         int x3, int y3, int x4, int y4)

{

  if ((x3 - x2)*(x4 - x1) > 0) return 0;

  if ((y3 - y2)*(y4 - y1) > 0) return 0;

  return 1;

}

 

int min(int x, int y)

{

  return (x < y) ? x : y;

}

 

int max(int x, int y)

{

  return (x > y) ? x : y;

}

 

int sgn(int x)

{

  return (x > 0) - (x < 0);

}

 

// A = (x1,y1), B = (x2,y2), C(x3,y3), D(x4,y4)

// return 1, if segments intersect

int intersect(int x1, int y1, int x2, int y2,

              int x3, int y3, int x4, int y4)

{

  int ABx, ABy, ACx, ACy, ADx, ADy;

  int CAx, CAy, CBx, CBy, CDx, CDy;

  int ACxAB, ADxAB, CAxCD, CBxCD;

  if (!RectanglesIntersects(min(x1, x2), min(y1, y2), max(x1, x2), max(y1, y2), min(x3, x4), min(y3, y4), max(x3, x4), max(y3, y4))) return 0;

 

  ACx = x3 - x1; ACy = y3 - y1;

  ABx = x2 - x1; ABy = y2 - y1;

  ADx = x4 - x1; ADy = y4 - y1;

 

  CAx = x1 - x3; CAy = y1 - y3;

  CBx = x2 - x3; CBy = y2 - y3;

  CDx = x4 - x3; CDy = y4 - y3;

 

  ACxAB = ACx * ABy - ACy * ABx;

  ADxAB = ADx * ABy - ADy * ABx;

  CAxCD = CAx * CDy - CAy * CDx;

  CBxCD = CBx * CDy - CBy * CDx;

 

  if ((sgn(ACxAB) * sgn(ADxAB) > 0) || (sgn(CAxCD) * sgn(CBxCD) > 0))

    return 0;

  return 1;

}

 

int Repr(int n)

{

  if (n == mas[n]) return n;

  return mas[n] = Repr(mas[n]);

}

 

int Union(int x, int y)

{

  int x1 = Repr(x), y1 = Repr(y);

  mas[x1] = y1;

  return (x1 != y1);

}

 

int main(void)

{

  scanf("%d", &tests);

  while (tests--)

  {

    scanf("%d %d", &n, &m);

    for (i = 1; i <= n; i++)

      scanf("%d %d %d %d", &ax[i], &ay[i], &bx[i], &by[i]);

 

    for (i = 1; i <= n; i++) mas[i] = i;

 

    for (i = 1; i <= n; i++)

    for (j = i + 1; j <= n; j++)

      if (intersect(ax[i], ay[i], bx[i], by[i], ax[j], ay[j], bx[j], by[j]))

        Union(i, j);

 

    for (i = 0; i < m; i++)

    {

      scanf("%d %d", &x, &y);

      if (Repr(x) == Repr(y)) puts("YES");

      else puts("NO");

    }

  }

 

  return 0;

}